/**
 * 21. 合并两个有序链表
 *
 * 【简单】
 *
 *
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg】
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 *
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 */

import { ListNode } from '../utils/list'

function mergeTwoLists(
	list1: ListNode | null,
	list2: ListNode | null
): ListNode | null {
	if (!list1) {
		return list2
	}
	if (!list2) {
		return list1
	}

	const dummy = new ListNode()
	let p = dummy

	while (list1 && list2) {
		if (list1.val! < list2.val!) {
			p.next = list1
			list1 = list1.next
		} else {
			p.next = list2
			list2 = list2.next
		}
		p = p.next!
	}

	p.next = list1 ? list1 : list2

	return dummy.next
}
